#include "../inc/max_palindrome.hpp"
#include <vector>
#include <iostream>
using namespace std;
int max_palindrome(string str, string &palindstr)
{
    //初始化二维vector
    vector<vector<int>> dp(str.length(), vector<int>(str.length(), 0));
    int maxpalind = 0;
    //先进行一次遍历统计长度为2和长度为1的dp
    //为以后递推长度为n的dp做准备
    for (size_t i = 0; i < str.length(); i++)
    {
        dp[i][i] = 1;
        if (i + 1 >= str.length())
        {
            break;
        }

        if (str[i] == str[i + 1])
        {
            dp[i][i + 1] = 1;
            maxpalind = 2;
        }
    }
    //"abcdcba"
    //外层循环控制长度
    for (int len = 3; len <= str.length(); len++)
    {
        //内层循环控制起始位置
        for (int i = 0; i + len - 1 < str.length(); i++)
        {
            //首尾相同并且去掉首尾后子串仍是回文串
            if (str[i] == str[i + len - 1] && dp[i + 1][i + len - 2] == 1)
            {
                //更新最大长度
                maxpalind = len;
                //更新dp标记，标记i~i+len-1为回文串
                dp[i][i + len - 1] = 1;
                palindstr = str.substr(i, i + len - 1);
            }
        }
    }
    return maxpalind;
}

int cal_maxlen(string str, int left, int right)
{
    while (left >= 0 && right < str.length() && str[left] == str[right])
    {
        left--;
        right++;
    }
    //因为边界以及左右值不等情况下，此时要-1
    // 假设字符串为abcbd 此时left 为0，right 为4=> 4-0-1=3
    return right - left - 1;
}

int center_expend(string str, string &palindstr)
{
    int maxpalind = 0;
    //从0开始遍历，直到字符串结尾
    for (int i = 0; i < str.length() - 1; i++)
    {
        //以单节点为中心扩展
        auto len2 = cal_maxlen(str, i, i);
        //以双节点为中心扩展
        auto len1 = cal_maxlen(str, i, i + 1);
        auto maxlen = 0;
        len2 > len1 ? maxlen = len2 : maxlen = len1;
        if (maxlen > maxpalind)
        {
            maxpalind = maxlen;
            //此处计算左右节点的位置
            //根据总长度maxlen折半找到起始位置
            // 假设字符串为abccba, i为2，maxlen为6
            //如果字符串为abcba,i为2，maxlen为5，下面规则同样适用
            auto start = i - (maxlen - 1) / 2;
            auto end = i + maxlen / 2;
            palindstr = str.substr(start, end + 1);
        }
    }

    return maxpalind;
}
